package algorithms.question.class11;

import common.util.MyUtil;

import java.util.Arrays;

/**
 * 判断一个字符串的L-R范围是否回文
 * 返回一个二维数组
 *
 * @author guichang
 * @date 2021/8/8
 */

@SuppressWarnings("all")
public class Code3_子串是否回文 {

    public static void main(String[] args) {
        String str = "abaadbada";
        boolean[][] sub = sub(str);
        MyUtil.print(sub[6][8]);
        for (int i = 0; i < sub.length; i++) {
            MyUtil.print(Arrays.toString(sub[i]));
        }
    }

    public static boolean[][] sub(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        char[] strs = str.toCharArray();
        int N = str.length();
        boolean[][] dp = new boolean[N][N];
        // 填充dp[i][i]
        for (int i = 0; i < N; i++) {
            dp[i][i] = true;
        }
        // 填充dp[i][i+1]
        for (int i = 0; i < N - 1; i++) {
            dp[i][i + 1] = strs[i] == strs[i + 1];
        }
        // 普遍位置 dp[i][j] = strs[i] == strs[j] && dp[i+1][j-1];
        for (int i = N - 3; i >= 0; i--) {
            for (int j = i + 2; j < N; j++) {
                dp[i][j] = strs[i] == strs[j] && dp[i + 1][j - 1];
            }
        }
        return dp;
    }


}